/*
 * @Author: gitee_com_zb
 * @Date: 2024-12-04 15:20:02
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-12-04 15:20:23
 * @FilePath: /algorithm/每日一题8.三数之和(medium).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/3sum?envType=problem-list-v2&envId=two-pointers
 */
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 基本思路:排序后,固定一个数a,找其他两数之和等于-a
        // 本质还是求两数之和问题
        // 注意本题需要去重
        std::sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        for (int i = 0; i < nums.size();) {
            if (nums[i] > 0) break; // 小优化,后面都是正数,三数之和不可能为0
            int left = i + 1, right = nums.size() - 1;
            int target = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum < target) left++;
                else if (sum > target) right--;
                else {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++, right--;
                    // 去重left和right
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重i
            i++;
            while (i < nums.size() && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

// class Solution {
// public:
//     vector<vector<int>> threeSum(vector<int>& nums) {
//         // 先排序，方便双指针处理
//         std::sort(nums.begin(), nums.end());
//         // 使用 set 存储结果三元组，避免重复
//         std::set<std::vector<int>> uniqueTriplets;
//         for (int i = 0; i < nums.size(); ++i) {
//             int left = i + 1, right = nums.size() - 1;
//             int target = -nums[i];
//             while (left < right) {
//                 int sum = nums[left] + nums[right];
//                 if (sum < target) {
//                     ++left;
//                 } else if (sum > target) {
//                     --right;
//                 } else {
//                     // 找到一个符合条件的三元组，插入 set
//                     uniqueTriplets.insert({nums[i], nums[left],
//                     nums[right]});
//                     ++left;
//                     --right;
//                 }
//             }
//         }
//         // 将 set 转换为 vector 进行返回
//         return vector<vector<int>>(uniqueTriplets.begin(),
//                                    uniqueTriplets.end());
//     }
// };